package slidingWindow;

import java.util.HashSet;
import java.util.Set;

public class LongestOnes {

    /**
     * 总结：动态滑动窗口从0开始，
     *
     * 给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
     *
     * 返回仅包含 1 的最长（连续）子数组的长度。
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
        int i = longestOnes2(nums, 3);
        System.out.println(i);
    }

    /**
     * 动态滑动窗口
     * 总结：要确保左界限小于右界限
     * @param nums
     * @param k
     * @return
     */
    public static int longestOnes(int[] nums, int k){
        int len = nums.length;
        //使用一个集合存储0->1的位置
        Set<Integer> set = new HashSet<>();
        //定义右边界
        int rk = 0;
        //定义结果
        int ans = 0;
        //进行窗口的滑动（动态滑动窗口）
        for (int i = 0; i < len; i++){
            if (i > rk){
                rk = i;
            }
            //右边界进行移动,不能一直移动，要有结束条件
            while ((rk<len) && (nums[rk]==1 || k > 0)){
                if (nums[rk]==0){
                    k--;
                    //记录下为0的位置
                    set.add(rk);
                }
                rk++;
            }
            //收集数值
            ans = Math.max(rk-i, ans);
            //左边界向右移动
            if (set.contains(i)){
                //曾经是0
                set.remove(i);
                k++;
            }
        }
        return ans;
    }
    //方法二：该问题也可以转化为求和的问题，
    public static int longestOnes2(int[] nums, int k){
        int len = nums.length;
        //记录0的个数
        int zero_sum = 0;
        //右边界
        int rk = 0;
        //初始化窗口大小为1
        zero_sum += 1 - nums[0];
        int ans = 0;
        //遍历顺序结构
        for (int i = 0; i < len; i++){
            //右边界右移，控制条件，必须满足条件才能够进行移动，不满足条件不能移动去移动右指针
            while (rk+1<len && zero_sum <= k){
                rk++;
                zero_sum += 1 - nums[rk];
            }
            //收集结果，只有在满足条件的时候才收集结果
            if (zero_sum > k){
                ans = Math.max(rk-i, ans);
            } else {
                ans = Math.max(rk-i+1, ans);
            }

            //左边界右移
            zero_sum -= 1 - nums[i];
        }
        return ans;
    }

    //复习：方法一
    public int longestOnes02(int[] nums, int k) {
        int len = nums.length;
        //记录0的位置，记录窗口中的数据，有时可以省略，合并到结果之中
        //HashSet<Integer> set = new HashSet<>();
        //右边界
        int right = -1;
        //记录结果
        int ans = 0;
        //进行遍历
        for (int i = 0; i < len; i++){
            //右边界向右移动,移动到满足条件的临界点，这一边界用于控制使得结果符合条件
            while (right + 1 < len && (k==0&&nums[right+1]==0?false:true)){//为true时，表明右边界可以移动到下一个位置，循环体中的内容是将循环体移动到下一个位置
                if (nums[right + 1] == 0){
                    //处理滑动窗口的内容
                    k--;
                    //记录为零的坐标，处理窗口中内容的变化
                    //set.add(right+1);
                }
                right++;
            }
            //由于前面的条件控制，到达这里的滑动窗口的大小为符合调节的结果
            ans = Math.max(right - i + 1, ans);
            //移动左边界，将左边界向右滑动，i++表示向右滑动了，这里处理滑动窗口的内容变化以及边界条件
            if (nums[i] == 0){
                k++;
            }
            //set.remove(i);
        }
        return ans;
    }
}
